#coding=utf-8 
'''
Created on 2012-10-27

@author: infear
'''
#http://blog.csdn.net/bitzhuxb/article/details/7539481
#2面
from LinkedNode import LinkedNode 
from LinkedNode import _print 
def reverseInt(i):
    if not i:
        return None
    else:
        if i%10==0:
            return reverseInt(i/10)
        else:
            list_i=list(str(i))
            i,j=0,len(list_i)-1
            while(i<j):
                list_i[i],list_i[j]=list_i[j],list_i[i]
                i,j=i+1,j-1
            return list_i

def reverseList(p):
    p1=None
    p2=p
    while p2 is not None:
        p3=p2.next
        p2.next=p1
        p1=p2
        p2=p3
    return p1

#m每隔N段逆序一次 
#注意每次生成一段之后要初始条件复原
def reverseListSegmentN(p,N):
    p1=None
    p2=p
    count=N
    while p2 is not None:
        while p2 is not None and count!=0:
            p3=p2.next
            p2.next=p1
            p1=p2
            p2=p3
            count=count-1
        yield p1
        p1=None
        count=N
    
#Given a head pointer pointing to a linked list ,please write a function that sort the list
#in increasing order. You are not allowed to use temporary array or memory copy
def sortList(head):
    if not head:
        return None
    next_head=sortList(head.next)
    if next_head:
        if head.value<next_head.value:
            head.next=next_head
            return head
        else:
            p1=next_head
            p2=next_head.next
            while p2 and p2.value<head.value:
                p1=p2
                p2=p2.next
            p1.next=head
            head.next=p2
            return next_head
    else:
        return head


print reverseInt(12345)   

nod1=LinkedNode(None,1)
nod2=LinkedNode(nod1,2)
nod3=LinkedNode(nod2,3)
nod4=LinkedNode(nod3,4)
nod5=LinkedNode(nod4,5) 
#test reverseSegment
#for node in reverseListSegmentN(nod5,2):
#    _print(node) 
             
_print(sortList(nod5))